Problema de busca

Em teoria da complexidade computacional e teoria da computabilidade, o problema de busca é um tipo de problema computacional representado por uma relação binária. Se R é uma relação binária tal que o dominio (R) ⊆ Γ⁺ e T é um máquina de Turing, então T calcula R se:

Se x é tal que existe algum y tal que R(x, y) então T aceita x com saída z tal que R(x, z) (pode haver vários y, e T só precisa encontrar um deles )
Se x é tal que não existe y tal que R(x, y) então T rejeita x

Intuitivamente, o problema consiste em encontrar uma estrutura y em um objeto x. Um algoritmo é dito para resolver o problema se ele se comporta da seguinte forma: se pelo menos uma estrutura correspondente existe, então uma ocorrência desta estrutura é emitida, caso contrário, o algoritmo pára com uma saída apropriada ("Item não encontrado" ou qualquer outra mensagem do gênero).

Por exemplo, esses problemas ocorrem muito frequentemente em teoria dos grafos, onde busca grafos para estruturas como em particular acoplamento, clique, conjunto independente, etc. são assuntos de interesse.

Observe que o grafo de uma função parcial é uma relação binária, e se T calcula uma função parcial, então há, no máximo, uma saída possível.

Uma relação R pode ser vista como um problema de busca, e uma máquina de Turing que calcula R também pode resolvê-lo. Todo problema de busca tem um correspondente problema de decisão

L(R)=\{x\mid \exists yR(x,y)\}.\,

Esta definição pode ser generalizada para relações N-ária usando qualquer codificação adequada que permite que várias sequências sejam comprimidas em uma cadeia de caracteres (por exemplo, listando-os consecutivamente com um delimitador).